Local Area Networks ("LAN") may operate using different topologies and protocols for providing stations on the LAN with access to communications facilities for communicating with one another and for sharing resources. In several widely used topologies, stations share a communication medium over which stations transmit data to one or more stations. Successful transmission of data by a station typically requires exclusive access to the medium. When more than one station has data to transmit at the same time, protocols may provide resources for resolving conflicts among the contending stations.
Various protocols for resolving contention among stations having data to transmit on the communications medium may be used. One widely used scheme is the Carrier Sense Multiple Access with Collision Detection ("CSMA/CD") protocol. The CSMA/CD is organized around layered protocols according to the Open Systems Interconnection ("OSI") reference model. The OSI model consists of seven layers including, from lowest-to-highest, a physical, data link, network, transport, session, application and presentation layer. The physical layer transmits bits over a communication link. The data link layer establishes and maintains point-to-point connections for the transmission of data frames.
The CSMA/CD protocol includes a data link layer with a Logical Link Control ("LLC") sub-layer and a Medium Access Control ("MAC") sub-layer. The LLC sub-layer handles logical links between stations while the MAC controls access to a communication medium via a physical layer. A CSMA/CD standard for Ethernet LANs is defined by Institute of Electrical and Electronic Engineers ("IEEE") 802.3 standard.
The CSMA/CD structure is a peer-to-peer network structure and stations on the network are vying for use of a channel when they have data to transmit. The contention can result in collisions that distort the transmission signals. Stations on the network cannot use distorted collision signals. A "collision window" is typically used to handle CSMA/CD collisions. A collision window describes the length of time required for a signal to propagate through the channel and to be detected by each station in the network.
Token bus LANs use a bus topology and provide access to a channel as if it were a ring. The token bus protocol is a collision-free protocol that uses a special frame called a "token" to govern which network station is allowed to send data. Capacity can be allocated through the use of priority classes. IEEE 802.4 defines a token bus LAN standard.
Token ring LANs connect participating stations in a ring topology; each station is connected to the medium via a ring interface unit. The ring interface unit is responsible for monitoring data passing through it as well as regenerating a signal and passing it to the next station. Token ring LANs use a token to determine which station may transmit, and also include a priority scheme. The object of the priority scheme is to give each station an opportunity to reserve the use of the ring for the next transmission around the ring. IEEE 802.5 defines a token ring LAN standard.
The CSMA/CD work reasonably well with large numbers of stations, but do not easily or efficiently support multiple priority classes or priority schemes. Also, their throughput performance suffers significantly in the presence of a high volume of network traffic. Token bus and token ring protocols with LLC and MAC can sustain relatively constant throughput even if the network traffic grows but they are typically more complex than CSMA/CD protocols.
In addition, contention resolution schemes that permit data collision in controlling access to the communication medium may operate adequately in small networks. In larger networks that have a higher number of stations, however, the overall throughput of the system degrades. This is because the probability of collision increases in systems in which the number of stations contending for access increases. One substantial component of the conflict resolution time is the time required to begin the transmission of data and to detect collisions. As the number of collisions increases, the time required to resolve the conflicts increases resulting in the degradation of the system throughput.
It is desirable, especially in the area of real-time services (e.g., teleconferencing), to have a contention resolution protocol which is simple, efficient, fair and distributed that can be used on a variety of computer network topologies (e.g., star, inverted tree, bus). The protocol should allow for a large number of network stations with differing priority class levels and delay requirements.
It is further desirable to provide a contention resolution scheme for networked stations to contend for resolution without the need to detect collisions.